package deuxieme_partie;

import java.util.*;

public class GrandEntier {

	private static final int B = 10;
	private static final int MAX_BIT_LENGTH = 10000000; 

	private LinkedList<Integer> terms;

	@SuppressWarnings("unchecked")
	public GrandEntier(LinkedList<Integer> ge)
	{
		if (ge.size() > MAX_BIT_LENGTH)
			throw new IllegalArgumentException("La liste de chiffres passée en paramètre est trop longue");
		
		this.terms = (LinkedList<Integer>)ge.clone();
	}
	
	public GrandEntier(int numBits, Random rnd)
	{
		this.terms = new LinkedList<Integer>();
		
		for (int i = 0; i < numBits; i++)
			this.terms.add(rnd.nextInt(B - 1));
	}
	
	public GrandEntier()
	{
		this(new LinkedList<Integer>());
	}
	
	public LinkedList<Integer> getTerms()
	{
		return this.terms;
	}

	/**
	 * Returns the String representation of this GrandEntier
	 * 
	 * @return
	 */
	@Override
	public String toString()
	{
		this.reduce();
		
		String str = "";
		for (Integer i : this.terms) 
		{
			if (i < 10)
				str += i;
			else
				switch (i)
				{
					case 10 : str += 'A'; break;
					case 11 : str += 'B'; break;
					case 12 : str += 'C'; break;
					case 13 : str += 'D'; break;
					case 14 : str += 'E'; break;
					case 15 : str += 'F'; break;
					default : str += 'X';
				}
		}

		return str;
	}
	
	/**
	 * Compares this GrandEntier with the specified Object for equality. 
	 * @return vrai si les grands entiers sont égaux faux sinon.
	 * 
	 * complexite if = Θ(1)
	 * complexite affectation = Θ(1)
	 * complexité appel a compareTo = Θ(n)
	 * 
	 * Complexité totale = Θ(n)
	 * 
	 * 
	 */
	@Override
	public boolean equals(Object o)
	{
		if (!(o instanceof GrandEntier))
			return false;

		GrandEntier ge = (GrandEntier)o;

		return (this.compareTo(ge) == 0);
	}

	/**
	 * Compares this GrandEntier with the specified GrandEntier
	 * 
	 * @param ge -  GrandEntier to which this GrandEntier is to be compared. 
	 * @return : -1, 0 or 1 as this GrandEntier is numerically less than, equal to, or greater than e.
	 * 
	 * complexite première partie = Θ(1)
	 * complexité boucle for = Θ(n)
	 * complexite if - else = Θ(1)
	 * 
	 * complexité totale = Θ(n)
	 */
	public int compareTo(GrandEntier ge)
	{	
		this.reduce();
		ge.reduce();
		
		if (this.length() > ge.length())
			return 1;
		else if (this.length() < ge.length())
			return -1;
		
		// Les deux nombres ont la même taille
		//
		int size = this.length();
		int nbThis, nbGe;
		for (int i = 0; i < size; i++)
		{
			nbThis = this.terms.get(i);
			nbGe = ge.terms.get(i);
			
			if (nbThis > nbGe)
				return 1;
			else if (nbThis < nbGe)
				return -1;
		}

		return 0;
	}

	/**
	 * Returns the size of this GrandEntier
	 * 
	 * @return
	 */
	public int length()
	{
		return this.terms.size();
	}
	
	/**
	 * Returns a GrandEntier with the value this * B^n
	 * 
	 * @param n
	 * @return 
	 * 
	 * addAll complexité = Θ(n)
	 * boucle for complexité = Θ(n)
	 * addLast complexité = Θ(1)
	 * 
	 * Complexité totale = Θ(n)
	 * 
	 */
	public GrandEntier shiftLeft(int n)
	{
		this.reduce();
		
		LinkedList<Integer> newValues = new LinkedList<Integer>();
		newValues.addAll(this.terms);
		
		for (int i = 0; i < n; i++)
			newValues.addLast(0);
		
		return new GrandEntier(newValues);
	}
	
	/**
	 * Returns a GrandEntier with the value this + ge
	 * 
	 * @param ge
	 * @return
	 * 
	 * complexité boucle for = Θ(n)
	 * addNumbers complexité = Θ(1)
	 * complexité addfirst = Θ(1)
	 * complexité affectation = Θ(1)
	 * 
	 * complexité derniere condition = Θ(1)
	 * 
	 * complexité totale = Θ(n)
	 * 
	 */
	public GrandEntier add(GrandEntier ge)
	{
		this.reduce();
		ge.reduce();
		
		LinkedList<Integer> result = new LinkedList<Integer>();
		
		// Mettre les deux nombres à taille égale
		//
		this.resizeWith(ge);
		
		if (this.length() != ge.length())
			throw new RuntimeException("Erreur d'algo. Tailles non égales.");
		
		int res[];
		int carry = 0;
		for (int i = this.length() - 1; i >= 0; i--)
		{			
			res = addNumbers(this.terms.get(i), ge.terms.get(i), carry);
			result.addFirst(res[0]);
			carry = res[1];
		}
		
		if (carry != 0)
			result.addFirst(carry);
		
		return new GrandEntier(result);
	}
	
	/**
	 * Returns a GrandEntier with the value abs(this - ge)
	 * 
	 * @param ge
	 * @return
	 * 
	 * complexité premiere partie = Θ(1)
	 * complexité boucle for = Θ(n)
	 * complexité subAbsoluteNumbers = Θ(1)
	 * complexité addfirst = Θ(1)
	 * 
	 * complexité totale = Θ(n)
	 */
	public GrandEntier subAbsolute(GrandEntier ge)
	{
		this.reduce();
		ge.reduce();
		
		GrandEntier longest, shortest;
		int resc = this.compareTo(ge);
		if (resc < 0)
		{
			longest = ge;
			shortest = this;
		}
		else if (resc > 0)
		{
			longest = this;
			shortest = ge;
		}
		else
			return new GrandEntier();
		
		LinkedList<Integer> result = new LinkedList<Integer>();
		
		// Mettre les deux nombres à taille égale
		//
		longest.resizeWith(shortest);
		
		int res[];
		int carry = 0;
		for (int i = this.length() - 1; i >= 0; i--)
		{			
			res = subAbsoluteNumbers(longest.getTerms().get(i), shortest.getTerms().get(i), carry);
			result.addFirst(res[0]);
			carry = res[1];
		}
		
		return new GrandEntier(result).reduce();
	}
	
	/**
	 * Multiplie le GrandEntier this avec le GrandEntier ge
	 * 
	 * @param ge
	 * @return
	 * 
	 * Avant la boucle for complexité = Θ(1)
	 * Premiere boucle for complexité = Θ(n)
	 * Boucle for imbriqué complexité = Θ(n)
	 * Dans la boucle for tout complexité des appels = Θ(1)
	 * complexité addFirst = Θ(1)
	 * Complexité shiftLeft = Θ(n)
	 * Complexité derniere boucle for = Θ(n)
	 * 
	 * Complexité totale = Θ(n²)
	 */
	public GrandEntier multiply(GrandEntier ge)
	{
		this.reduce();
		ge.reduce();
		
		GrandEntier result = new GrandEntier();
		
		// Mettre les deux nombres à tailles égales
		this.resizeWith(ge);
		
		if (this.length() != ge.length())
			throw new RuntimeException("Erreur d'algo. Tailles non égales.");
		
		int res[];
		int carry = 0;
		int shift = 0;
		LinkedList<GrandEntier> coeffs = new LinkedList<GrandEntier>();
		LinkedList<Integer> currentCoeff;
		for (int i = this.length() - 1; i >= 0; i--)
		{	
			carry = 0;
			currentCoeff = new LinkedList<Integer>();
			for (int j = ge.length() - 1; j >= 0; j--)
			{
				res = multiplyNumbers(this.terms.get(i), ge.getTerms().get(j), carry);
				currentCoeff.addFirst(res[0]);
				carry = res[1];
			}
			
			if (carry != 0)
				currentCoeff.addFirst(carry);
			
			coeffs.addLast(new GrandEntier(currentCoeff).shiftLeft(shift));
			
			shift ++;
		}
		
		for (GrandEntier g : coeffs)
			result = result.add(g);
		
		return result;
	}
	
	/**
	 * Multiplie le GrandEntier this avec le GrandEntier ge
	 * en utilisant l'algorithme de Karatsuba
	 * 
	 * @param ge
	 * @return
	 * 
	 * On neglige la complexité des methode takeHalfNumber
	 * Premiere condition appel a multiply, complexité = Θ(n²)
	 * Deuxième condition appel récursif
	 * On appelle recursivement la methode avec la moitié du grandEntier
	 * 1 fois dans quotient
	 * 2 fois dans les multiply / multiplyFast
	 * C(n) = 3 * C(n/2) * n²
	 * 
	 * Complexité compareTo = Θ(n)
	 * Complexité du calcul de quo = Θ(n²)
	 * 			Θ(n)+Θ(n²)+Θ(n)
	 * Complexité du calcul de res = Θ(n)
	 * 
	 * D'après le cours avec cette formule on obtient une complexité = O(n^log2(3))
	 * Complexité théorique = O(n^log2(3))
	 */
	public GrandEntier multiplyFast(GrandEntier ge)
	{		
		GrandEntier a1 = this.takeHalfNumber(true);
		GrandEntier b1 = ge.takeHalfNumber(true);
		GrandEntier a2 = this.takeHalfNumber(false);
		GrandEntier b2 = ge.takeHalfNumber(false);
		
		GrandEntier nb1, nb2;
		if (this.length() == 2 && ge.length() == 2)
		{
			nb1 = a1.multiply(b1);
			nb2 = a2.multiply(b2);
		}
		else if (this.length() % 2 == 0 && ge.length() % 2 == 0)
		{
			nb1 = a1.multiplyFast(b1);
			nb2 = a2.multiplyFast(b2);
		}
		else
			throw new RuntimeException("L'algorithme de Karatsuba n'a pas été programmé pour calculer des produits de taille " + 
					this.length() + " * " + ge.length());
		
		// Récupérer le signe des différences
		//
		boolean s1 = (a1.compareTo(a2) >= 0);
		boolean s2 = (b1.compareTo(b2) >= 0);
		
		// Calcul de la valeur absolue du quotient
		//
		GrandEntier quo = a1.subAbsolute(a2).multiply(b1.subAbsolute(b2));
		
		// Add ou Sub du quotient en fonction du signe des différences lors du calcul du résultat final
		//
		GrandEntier res = (s1 == s2) ? nb1.shiftLeft(this.length()).add(nb1.add(nb2).subAbsolute(quo).shiftLeft(this.length() / 2)).add(nb2)
				: nb1.shiftLeft(this.length()).add(nb1.add(nb2).add(quo).shiftLeft(this.length() / 2)).add(nb2);
		
		return res.reduce();
	}
	
	/**
	 * Additionne les trois nombres passés en paramètre en base B,
	 * et retourne le resultat sous forme d'un tableau où l'élément
	 * à l'indice 0 est le résultat de l'addition, et l'élément à
	 * l'indice 1 est la valeur de l'éventuelle retenue
	 * 
	 * @param i
	 * @param j
	 * @param c
	 * @return
	 * 
	 * Ici il n'y a que des calculs simple et des affectations
	 * complexité totale = Θ(1)
	 */
	private static int[] addNumbers(int i, int j, int c)
	{
		Integer res = i + j + c;
		
		int toReturn[] = new int[2];
		
		// Retenue
		int rest = res % B;
		int carry = (res >= B) ? (res / B) : 0;
		
		toReturn[0] = rest;
		toReturn[1] = carry;
		
		return toReturn;
	}
	
	/**
	 * 
	 * @param i
	 * @param j
	 * @param c
	 * @return
	 * 
	 * Ici il n'y a que des calculs simple et des affectations
	 * complexité totale = Θ(1)
	 */
	private static int[] subAbsoluteNumbers(int i, int j, int c)
	{
		Integer res = (i - j) - c;
		
		int toReturn[] = new int[2];
		
		int carry = (res >= 0) ? 0 : 1;
		int rest = (res >= 0) ? res : B + res;
		
		toReturn[0] = rest;
		toReturn[1] = carry;
		
		return toReturn;
	}
	
	/**
	 * Multiplie les trois nombres passés en paramètre en base B,
	 * et retourne le resultat sous forme d'un tableau où l'élément
	 * à l'indice 0 est le résultat du produit, et l'élément à
	 * l'indice 1 est la valeur de l'éventuelle retenue
	 * 
	 * @param i
	 * @param j
	 * @param c
	 * @return
	 */
	private static int[] multiplyNumbers(int i, int j, int c)
	{
		Integer res = (i * j) + c;
		
		int toReturn[] = new int[2];
		
		// Retenue
		int rest = res % B;
		int carry = (res >= B) ? (res / B) : 0;
		
		toReturn[0] = rest;
		toReturn[1] = carry;
		
		return toReturn;
	}
	
	/**
	 * Met les deux nombres à tailles égales 
	 * (rajoute des 0 au plus court)
	 * 
	 * @param ge
	 * 
	 * complexité O(n) des deux boucles for
	 * complexité totale = O(n)
	 * 
	 */
	private void resizeWith(GrandEntier ge)
	{
		int diff = this.length() - ge.length();

		if (diff < 0)
		{
			diff = Math.abs(diff);
			for (int i = 0; i < diff; i++)
				this.terms.addFirst(0);
		}
		else if (diff > 0)
		{
			for (int i = 0; i < diff; i++)
				ge.terms.addFirst(0);
		}
	}
	
	/**
	 * Simplifie le GrandEntier this (supprime les 0 en tête)
	 * 
	 * @return
	 * 
	 * complexité boucle while O(n)
	 * complexité totale O(n)
	 */
	private GrandEntier reduce()
	{
		while (this.terms.size() > 0 && this.terms.get(0) == 0)
			this.terms.remove(0);
		
		return this;
	}
	
	/**
	 * Retourne la moitié du nombre
	 * 
	 * complexité O(n)
	 * 
	 * @param start : détermine si on prend la première ou la seconde moitié
	 * @return
	 */
	private GrandEntier takeHalfNumber(boolean start)
	{
		LinkedList<Integer> l = new LinkedList<Integer>();
		
		int indStart = start ? 0 : (this.length() / 2);
		int indEnd = start ? this.length() / 2 : this.length();
		
		for (int i = indStart; i < indEnd; i++)
			l.addLast(this.terms.get(i));
		
		return new GrandEntier(l);
	}
	
	/**
	* compare experimentalement les temps de calculs moyens de multiply et multiplyFast
	* pour des entiers générés aléatoirement
	*/

	public static void compareSimpleWithFast(int n) throws Exception 
	{
	   Random r = new Random(); // génère des nombres pseudo aléatoires
	   long fixedSeed = r.nextLong();
	   long t0; //heure initiale d'une serie de tests de multiplication
	   long simpleTime; // heure finale d'une serie de tests de multiply
	   long fastTime; // heure finale d'une serie de tests de multiplyFast
	   
	   GrandEntier a, b; // les nombres à multiplier
	   System.out.println("\n\n\n");
	   System.out.println("Comparaison experimentale de la complexité de multiply et de multiplyFast");
	   System.out.println("-----------------------------------------------------------\n") ;
	   System.out.println("Nombre de répétitions pour chaque taille: "+n+"\n");
	   System.out.println("       || temps moyen | temps moyen ");
	   System.out.println("# bits || multiply    | multiplyFast ");
	   System.out.println("----------------------------------");
	   
	   for(int l=2; l <= MAX_BIT_LENGTH; l*=2)
	   {
	      r.setSeed(fixedSeed);
	      System.gc(); //nettoyage pour avoir des résultats plus significatifs
	      t0 = System.currentTimeMillis();
	      
	      for(int i=1; i<=n; i++)
	      {
	         a = new GrandEntier(l,r);
	         b = new GrandEntier(l,r);
	    	 a.multiply(b);
	      }
	      
	      simpleTime = System.currentTimeMillis()-t0;
	      r.setSeed(fixedSeed); // pour générer les memes nombres pseudoaléatoire
	      System.gc(); //nettoyage pour avoir des résultats plus significatifs
	      t0 = System.currentTimeMillis();
	      
	      for(int i=1; i<=n; i++)
	      {
	         a = new GrandEntier(l,r);
	         b = new GrandEntier(l,r);
	         a.multiplyFast(b);
	      }
	      
	      fastTime = System.currentTimeMillis()-t0;
	      System.out.println(l+" || "+simpleTime/n+" | "+fastTime/n);
	   }
	}	
}
